import numpy as np
from Core.individual import *

'''
GA主算法类
loop : 选择 -> 交叉 -> 变异
'''


class GA:
    def __init__(self, city_num=0, index_dict=None, dist_mat=None, population_num=0,
                 cross_rate=0.0, cross_point=0, mutation_rate=0.0):
        # 城市数量
        self.city_num = city_num
        # 坐标字典
        self.index_dict = index_dict
        # 距离矩阵
        self.dist_mat = dist_mat
        # 种群数量
        self.population_num = population_num
        # 种群中最佳个体(适应度最高)
        self.best_one = None
        # 交叉率
        self.cross_rate = cross_rate
        # 交叉点(单点交叉)
        self.cross_point = cross_point
        # 变异率
        self.mutation_rate = mutation_rate

    def init_population(self, population_list):
        """
        初始化种群 --> 初始种群(直接使用源个体的列表作为基因序列, 不涉及额外编码操作)
        分为两种情况:
            一种是算法伊始, 种群为空, 随机生成种群
            另一种是上一轮迭代遗传完的种群来到这一轮迭代
        :return:
        """
        p_list = []
        if len(population_list) == 0:
            for i in range(self.population_num):
                p_list.append(Individual(genes_len=self.city_num, dist_mat=self.dist_mat))
            np.random.shuffle(population_list)
        else:
            p_list = population_list
        self.best_one = self.get_best_individual(p_list)
        return p_list

    def select(self, p_list):
        """
        选择操作(轮盘赌法)
        **由于本题是求最短路径, 所以应该是fitness更小的个体"适应度更高"**
        1.p_recip_fitness为原始种群个体适应度的倒数数组
        2.p_probability储存每个个体被选中的概率
        3.probability_distribution存储概率分布(和)
        4.p_select为选择完的新种群
        :param p_list: 
        :return: 
        """
        p_recip_fitness = []
        p_select = []
        p_probability = []
        probability_distribution = []
        p_sum = 0
        # 对种群中所有个体适应度求倒数
        self.cal_list_reciprocal(p_recip_fitness, p_list)
        # 对种群中所有个体适应度求和
        for i in range(self.population_num):
            p_sum += p_recip_fitness[i]
        # 将概率值写入p_probability数组, 确定轮盘上每块的概率值
        for i in range(self.population_num):
            p_probability.append(p_recip_fitness[i] / p_sum)
        # 模拟轮盘上的概率分布
        for i in range(self.population_num):
            if i == 0:
                probability_distribution.append(p_probability[i])
            else:
                probability_distribution.append(probability_distribution[i - 1] + p_probability[i])
        # 开始选择操作, 选择的数量和初始种群保持一致, 按概率选择
        for i in range(self.population_num):
            # 生成一个[0, 1]的随机数
            rand_num = np.random.uniform(0, 1)
            # 检查这个随机数落在概率分布的哪一块, 对应的个体就是本轮循环选择的
            for j in range(len(probability_distribution)):
                if j == 0:
                    if rand_num < probability_distribution[j]:
                        p_select.append(p_list[j])
                        # 本轮轮盘赌选择完直接结束本轮
                        break
                else:
                    if (rand_num >= probability_distribution[j - 1]) and (rand_num < probability_distribution[j]):
                        p_select.append(p_list[j])
                        break
        return p_select

    def cross(self, p_select):
        """
        交叉操作
        采用单点交叉的方式 --> 交叉交叉点后半段基因片段
        注意: 交叉操作改变了genes数组, 遍历城市顺序改变了, 要重新计算适应度函数, 故需重新生成Individual对象
        # 由于种群中的每个个体都包含所有的城市(旅行商要遍历所有城市)
        # 所以此处两个体直接交换基因会出现重复的问题, 因此此处的交换定义为在要交叉的两个个体本体中找到
        # 对应要交换的基因座上的基因进行交换, 即实际上交换的是自己基因座上的基因
        :param p_select:
        :return:
        """
        # 交叉后的新生代数组
        p_cross = []
        # 随机化种群
        np.random.shuffle(p_select)
        # 开始交叉
        for i in range(0, self.population_num):
            # 判定末尾个体交叉情况
            if i == self.population_num - 1:
                # 让末尾个体去和第一个个体交叉
                tmp_father = p_select[i]
                tmp_mother = p_select[0]
            else:
                tmp_father = p_select[i]
                tmp_mother = p_select[i + 1]
            # 先判断是否发生交叉, 这里仍然使用轮盘赌思想 -> [0, cross_rate]发生交叉, 否则不交叉
            rand_num = np.random.uniform(0, 1)
            if rand_num > self.cross_rate:
                # 不交叉直接添加为后代
                p_cross.append(tmp_father)
                continue
            # 从设定的交叉点开始交叉
            for j in range(self.cross_point, self.city_num):
                # 在"father"中找到与"mother"对应基因座上值相同的索引位置
                father_pos = tmp_father.genes.index(tmp_mother.genes[j])
                # 执行交叉操作
                tmp_father.genes[j], tmp_father.genes[father_pos] = tmp_father.genes[father_pos], tmp_father.genes[j]
                # tmp_mother.genes[j], tmp_mother.genes[mother_pos] = tmp_mother.genes[mother_pos], tmp_mother.genes[j]
            # 产生后代, 每次交叉两个个体只产生一个后代, 因为种群个体奇偶数原因
            # 交叉操作改变了genes数组, 遍历城市顺序改变了, 要重新计算适应度函数, 故需重新生成Individual对象
            # 使用交叉后的父类基因生成子类个体, 子类重新计算适应度
            p_cross.append(Individual(genes=tmp_father.genes, genes_len=self.city_num, dist_mat=self.dist_mat))
        return p_cross

    def mutation(self, p_cross):
        """
        变异操作
        采用单基因随机变异的方式
        首先先判断是否会发生变异, 不足一位则不进行变异操作
        :param p_cross:
        :return:
        """
        p_mutation = p_cross
        # 先判断是否会发生变异, 不足一位则不进行变异操作
        mutation_num = self.city_num * self.population_num * self.mutation_rate
        if mutation_num >= 1:
            # 将变异的基因数取整, 向下取整
            mutation_num = int(mutation_num)
            # 模拟开始, 随机变异, 一次只变异基因座上的某一位
            for i in range(mutation_num):
                # 先随机选出种群中变异的个体
                rand_individual = np.random.randint(0, self.population_num - 1)
                # 取出这个个体进行变异(要在源列表中删除它, 因为要改变基因序列, 适应度需要重新计算)
                individual_ = p_mutation[rand_individual]
                p_mutation.remove(individual_)
                # 随机变异该个体中的某一位, 由于题目的限制(需要遍历所有城市), so同样采用交换的方式
                mutation_index = np.random.randint(0, self.city_num)
                rand_index = np.random.randint(0, self.city_num)
                # 交换(变异)
                individual_.genes[mutation_index], individual_.genes[rand_index] = individual_.genes[rand_index], \
                                                                                   individual_.genes[mutation_index]
                # 产生新子类
                p_mutation.append(Individual(genes=individual_.genes, genes_len=self.city_num, dist_mat=self.dist_mat))
        return p_mutation

    @staticmethod
    def get_best_individual(population_list):
        """
        获取某种群中最大适应度个体, 事实上应该是适应度最小的那个数
        :param population_list:
        :return:
        """
        the_best = population_list[0]
        for i in range(1, len(population_list)):
            if the_best.fitness > population_list[i].fitness:
                the_best = population_list[i]
        return the_best

    def cal_list_reciprocal(self, p_recip_fitness, p_list):
        """
        **由于本题是求最短路径, 所以应该是fitness更小的个体"适应度更高"**
        取倒数函数
        :param p_recip_fitness:
        :return:
        """
        for i in range(self.population_num):
            p_recip_fitness.append(1 / p_list[i].fitness)


if __name__ == '__main__':
    '''
    Test
    '''
    # 城市数量
    city_num = 15
    # 种群数量
    population_num = 13
    # 交叉率 [0,1] **建议设置大一些
    cross_rate = 0.9
    # 交叉点 [0, city_num - 1] -> 单点交叉, 两个体互换交叉点后面基因座上的基因
    cross_point = 7
    # 变异率 [0, 1] -> 变异提供了搜索随机性, 但不可调过大
    mutation_rate = 0.05

    index_dict = index_dict_init(city_num)
    # 获得城市间距离矩阵
    dist_mat = distance_matrix_init(index_dict, city_num)

    # 实例化对象
    my_ga = GA(city_num=city_num, index_dict=index_dict, dist_mat=dist_mat, population_num=population_num,
               cross_rate=cross_rate, cross_point=cross_point, mutation_rate=mutation_rate)
    population_list = []
    p_list = my_ga.init_population(population_list)
    p_select = my_ga.select(p_list)
    p_cross = my_ga.cross(p_select)
    my_ga.mutation(p_cross)
